// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/value-numbering-reducer.h"

#include <cstring>

#include "src/base/functional.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/node.h"

namespace v8 {
namespace internal {
    namespace compiler {

        ValueNumberingReducer::ValueNumberingReducer(Zone* temp_zone, Zone* graph_zone)
            : entries_(nullptr)
            , capacity_(0)
            , size_(0)
            , temp_zone_(temp_zone)
            , graph_zone_(graph_zone)
        {
        }

        ValueNumberingReducer::~ValueNumberingReducer() = default;

        Reduction ValueNumberingReducer::Reduce(Node* node)
        {
            if (!node->op()->HasProperty(Operator::kIdempotent))
                return NoChange();

            const size_t hash = NodeProperties::HashCode(node);
            if (!entries_) {
                DCHECK_EQ(0, size_);
                DCHECK_EQ(0, capacity_);
                // Allocate the initial entries and insert the first entry.
                capacity_ = kInitialCapacity;
                entries_ = temp_zone()->NewArray<Node*>(kInitialCapacity);
                memset(entries_, 0, sizeof(*entries_) * kInitialCapacity);
                entries_[hash & (kInitialCapacity - 1)] = node;
                size_ = 1;
                return NoChange();
            }

            DCHECK(size_ < capacity_);
            DCHECK(size_ + size_ / 4 < capacity_);

            const size_t mask = capacity_ - 1;
            size_t dead = capacity_;

            for (size_t i = hash & mask;; i = (i + 1) & mask) {
                Node* entry = entries_[i];
                if (!entry) {
                    if (dead != capacity_) {
                        // Reuse dead entry that we discovered on the way.
                        entries_[dead] = node;
                    } else {
                        // Have to insert a new entry.
                        entries_[i] = node;
                        size_++;

                        // Resize to keep load factor below 80%
                        if (size_ + size_ / 4 >= capacity_)
                            Grow();
                    }
                    DCHECK(size_ + size_ / 4 < capacity_);
                    return NoChange();
                }

                if (entry == node) {
                    // We need to check for a certain class of collisions here. Imagine the
                    // following scenario:
                    //
                    //  1. We insert node1 with op1 and certain inputs at index i.
                    //  2. We insert node2 with op2 and certain inputs at index i+1.
                    //  3. Some other reducer changes node1 to op2 and the inputs from node2.
                    //
                    // Now we are called again to reduce node1, and we would return NoChange
                    // in this case because we find node1 first, but what we should actually
                    // do is return Replace(node2) instead.
                    for (size_t j = (i + 1) & mask;; j = (j + 1) & mask) {
                        Node* entry = entries_[j];
                        if (!entry) {
                            // No collision, {node} is fine.
                            return NoChange();
                        }
                        if (entry->IsDead()) {
                            continue;
                        }
                        if (entry == node) {
                            // Collision with ourselves, doesn't count as a real collision.
                            // Opportunistically clean-up the duplicate entry if we're at the end
                            // of a bucket.
                            if (!entries_[(j + 1) & mask]) {
                                entries_[j] = nullptr;
                                size_--;
                                return NoChange();
                            }
                            // Otherwise, keep searching for another collision.
                            continue;
                        }
                        if (NodeProperties::Equals(entry, node)) {
                            Reduction reduction = ReplaceIfTypesMatch(node, entry);
                            if (reduction.Changed()) {
                                // Overwrite the colliding entry with the actual entry.
                                entries_[i] = entry;
                                // Opportunistically clean-up the duplicate entry if we're at the
                                // end of a bucket.
                                if (!entries_[(j + 1) & mask]) {
                                    entries_[j] = nullptr;
                                    size_--;
                                }
                            }
                            return reduction;
                        }
                    }
                }

                // Skip dead entries, but remember their indices so we can reuse them.
                if (entry->IsDead()) {
                    dead = i;
                    continue;
                }
                if (NodeProperties::Equals(entry, node)) {
                    return ReplaceIfTypesMatch(node, entry);
                }
            }
        }

        Reduction ValueNumberingReducer::ReplaceIfTypesMatch(Node* node,
            Node* replacement)
        {
            // Make sure the replacement has at least as good type as the original node.
            if (NodeProperties::IsTyped(replacement) && NodeProperties::IsTyped(node)) {
                Type replacement_type = NodeProperties::GetType(replacement);
                Type node_type = NodeProperties::GetType(node);
                if (!replacement_type.Is(node_type)) {
                    // Ideally, we would set an intersection of {replacement_type} and
                    // {node_type} here. However, typing of NumberConstants assigns different
                    // types to constants with the same value (it creates a fresh heap
                    // number), which would make the intersection empty. To be safe, we use
                    // the smaller type if the types are comparable.
                    if (node_type.Is(replacement_type)) {
                        NodeProperties::SetType(replacement, node_type);
                    } else {
                        // Types are not comparable => do not replace.
                        return NoChange();
                    }
                }
            }
            return Replace(replacement);
        }

        void ValueNumberingReducer::Grow()
        {
            // Allocate a new block of entries double the previous capacity.
            Node** const old_entries = entries_;
            size_t const old_capacity = capacity_;
            capacity_ *= 2;
            entries_ = temp_zone()->NewArray<Node*>(capacity_);
            memset(entries_, 0, sizeof(*entries_) * capacity_);
            size_ = 0;
            size_t const mask = capacity_ - 1;

            // Insert the old entries into the new block (skipping dead nodes).
            for (size_t i = 0; i < old_capacity; ++i) {
                Node* const old_entry = old_entries[i];
                if (!old_entry || old_entry->IsDead())
                    continue;
                for (size_t j = NodeProperties::HashCode(old_entry) & mask;;
                     j = (j + 1) & mask) {
                    Node* const entry = entries_[j];
                    if (entry == old_entry) {
                        // Skip duplicate of the old entry.
                        break;
                    }
                    if (!entry) {
                        entries_[j] = old_entry;
                        size_++;
                        break;
                    }
                }
            }
        }

    } // namespace compiler
} // namespace internal
} // namespace v8
